package DoExercise.HSP_ZCY.A008_树.A001_普通二叉树;

/**
 * @Author: Du
 * @Date: 2021/7/13 12:21
 */
public class C11_后继节点
{
    
    public static class Node
    {
        public int value;
        public Node left;
        public Node right;
        public Node parent;
        
        public Node(int data)
        {
            this.value = data;
        }
    }
    
    
    /**
     * 中序遍历：
     * 有右树
     * 1、当前节点，右节点的最左节点
     * 无右树
     * 1、找父节点，且我是该父节点的第一个左节点，根据左 根 右，代表我是左，父节点就是下一个根
     * 找X的后继节点：某一组父子关系，父是子的左节点，OK
     *
     * @param node
     * @return
     */
    public static Node getSuccessorNode(Node node)
    {
        if (node == null)
        {
            return null;
        }
        if (node.right != null)//左 根 右，
        {
            return getLeftMost(node.right);
        } else
        {//无右子树，找当前节点的左子树
            Node parent = node.parent;
            while (parent != null && parent.right == node)
            {
                node = parent;
                parent = node.parent;
            }
            return parent;//返回null 或者 parent.left
        }
    }
    
    /**
     * 右树的最左节点
     *
     * @param node
     * @return
     */
    public static Node getLeftMost(Node node)
    {
        if (node == null) return null;
        while (node.left != null)
        {
            node = node.left;
        }
        return node;
    }
    
    public static void main(String[] args)
    {
        Node head = new Node(6);
        head.parent = null;
        head.left = new Node(3);
        head.left.parent = head;
        head.left.left = new Node(1);
        head.left.left.parent = head.left;
        head.left.left.right = new Node(2);
        head.left.left.right.parent = head.left.left;
        head.left.right = new Node(4);
        head.left.right.parent = head.left;
        head.left.right.right = new Node(5);
        head.left.right.right.parent = head.left.right;
        head.right = new Node(9);
        head.right.parent = head;
        head.right.left = new Node(8);
        head.right.left.parent = head.right;
        head.right.left.left = new Node(7);
        head.right.left.left.parent = head.right.left;
        head.right.right = new Node(10);
        head.right.right.parent = head.right;
        
        Node test = head.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.left.right.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.left.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.left;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right;
        System.out.println(test.value + " next: " + getSuccessorNode(test).value);
        test = head.right.right; // 10's next is null
        System.out.println(test.value + " next: " + getSuccessorNode(test));
    }
}
